package leetcode16

import (
	"math"
)

func threeSumClosest(nums []int, target int) int {
	var (
		res int
		sum int
	)

	nums = quickSort(nums)
	if len(nums) <= 0 {
		return res
	}
	res = nums[0] + nums[1] + nums[2]
	for i := 0; i < len(nums)-2; i++ {
		left := i + 1
		right := len(nums) - 1
		// 值
		// 小于则变大

		for left < right {
			sum = nums[i] + nums[left] + nums[right]
			if sum == target {
				return target
			}
			res = recent(res, sum, target)
			if sum > target {
				right--
			} else {
				left++
			}
		}
	}
	return res
}

func recent(res, cur, target int) int {
	if math.Abs(float64(target-res)) > math.Abs(float64(target-cur)) {
		res = cur
	}
	return res
}

func quickSort(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	mid := nums[0]
	var (
		left  []int
		mids  []int
		right []int
	)
	for i := 0; i < len(nums); i++ {
		if nums[i] < mid {
			left = append(left, nums[i])
		} else if nums[i] > mid {
			right = append(right, nums[i])
		} else {
			mids = append(mids, mid)
		}
	}
	return append(append(quickSort(left), mids...), quickSort(right)...)
}
